#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef struct TREENODE TreeNode;
typedef struct STROPT StrOpt;
typedef char NodeType[20];
struct TREENODE{
	NodeType Node;
	//char Node[20];
	TreeNode *Left;
	TreeNode *Right;
};
struct STROPT{
	char *Exp;
	int Ptr;
};
StrOpt* StrInit(char*);
_Bool GetNext(StrOpt*,char *dst);
TreeNode *BuildTree(char*);
TreeNode *NewNode(NodeType);
void MidOrder(TreeNode*);
void PostOrder(TreeNode*);

int main(){
	char Exp[]="  123 + 456 * abcde  ";
	//StrOpt *s=StrInit(Exp);
	//char ret[20];
	//int i=1;
	//while( GetNext(s,ret) ){
	//	printf("%3d:%s\n",i++,ret);
	//}
	TreeNode *exp=BuildTree(Exp);
	MidOrder(exp);
	printf("\n");
	PostOrder(exp);
	return 0;
}

StrOpt* StrInit(char* Exp){
	StrOpt *s=malloc(sizeof(StrOpt));
	s->Exp=Exp;
	s->Ptr=0;
	return s;
}
_Bool GetNext(StrOpt *s,char *dst){
	//if( s->Exp[Ptr] == '\0' )return false;
	char tmp[20];
	int i=0;
	char *p=s->Exp+s->Ptr;
	while( *p == ' ' && *p != '\0' )p++;		// ignore font sp
	while( *p != ' ' && *p != '\0' ){
		tmp[i++]=*(p++);
	}
	tmp[i]='\0';
	s->Ptr=p-s->Exp;
	if( tmp[0] == '\0' )
		return false;
	else{
		memcpy(dst,tmp,sizeof(char)*(i+1));
		return true;
	}
}
TreeNode *BuildTree(char* s){
	TreeNode *op1=NULL;
	TreeNode *sym=NULL;
	TreeNode *op2=NULL;
	NodeType tmp;
	StrOpt *st=StrInit(s);
	if( !GetNext(st,tmp) )
		return op1;
	op1=NewNode(tmp);
printf("First Op1:%s\n",op1->Node);
	while( GetNext(st,tmp) ){
		sym=NewNode(tmp);
printf("sym:%s\n",sym->Node);
		GetNext(st,tmp);
		op2=NewNode(tmp);
printf("op2:%s\n",op2->Node);
		sym->Left=op1;
		sym->Right=op2;
		op1=sym;
	}
	return op1;
}
TreeNode *NewNode(NodeType nt){
	TreeNode *t=malloc(sizeof(TreeNode));
	strcpy(t->Node,nt);
	t->Left=t->Right=NULL;
	return t;
}
void MidOrder(TreeNode* t){
	if( t ){
		MidOrder(t->Left);
		printf("%s ",t->Node);
		MidOrder(t->Right);
	}
	return;
}
void PostOrder(TreeNode *t){
	if( t ){
		PostOrder(t->Left);
		PostOrder(t->Right);
		printf("%s ",t->Node);
	}
	return;
}
